#ifndef   TEST_H
#define   TEST_H

#include "CGR.h"

double  CGR::computeSubnetEdgeWeight ( TwoTerCoarseNet &snet ) {
  double  subnet_weight = 0;
  for ( set<int>::iterator itr_edge = snet.edges.begin(); itr_edge != snet.edges.end(); itr_edge++ )
    subnet_weight += cgr.E[*itr_edge].weight;
  return  subnet_weight;
}


  bool  CGR::isInSegment ( int vxs, Segment seg ) {
    if ( vxs < seg.s || vxs > seg.t )
      return  false;
    bool  isNodeInSegment;
    if ( seg.type == "HORIZ" ) {
      isNodeInSegment = (V[vxs].x>=V[seg.s].x && V[vxs].x<=V[seg.t].x && V[vxs].y==V[seg.s].y && V[vxs].z==V[seg.s].z);
    }
    if ( seg.type == "VERT" ) {
      isNodeInSegment = (V[vxs].y>=V[seg.s].y && V[vxs].y<=V[seg.t].y && V[vxs].z==V[seg.s].z && V[vxs].x==V[seg.s].x);
    }
    if ( seg.type == "VIA" ) {
      isNodeInSegment = (V[vxs].z>=V[seg.s].z && V[vxs].z<=V[seg.t].z && V[vxs].x==V[seg.s].x && V[vxs].y==V[seg.s].y);
    }
    return  isNodeInSegment;
  }

int   CGR::xyzToGridNetTerminalId ( int x, int y, int z ) {
  assert ( x>=0 && x < fullGridX );
  assert ( y>=0 && y < fullGridY );
  assert ( z>=0 && z < numLayers );
  return  ( z*fullGridY*fullGridX + y*fullGridX + x );
}

  int     CGR::return_edge_id ( int i, int j, int k, int type ) {
    if ( type==0 )
      return  k*edgeCount2D+j*(fullGridX-1)+i;
    if ( type==1 )
      return  k*edgeCount2D+ fullGridY*(fullGridX-1) + i*(fullGridY-1)+ j;
    if ( type==2 )
      return  numLayers*edgeCount2D + ( j*fullGridX + i ) * (numLayers-1) + k;
    exit(0);
  }

bool    CGR::isInBox ( int node_id, GridBox &box ) {
  int x_coordinate = V[node_id].x;
  int y_coordinate = V[node_id].y;
  return  ( x_coordinate >= box.x0 && x_coordinate < box.x0+box.dx && y_coordinate >= box.y0 && y_coordinate < box.y0+box.dy );
}

bool    CGR::isOnBoundary ( int node_id, GridBox &box ) {
  int x_coordinate = V[node_id].x;
  int y_coordinate = V[node_id].y;
  return  ( (x_coordinate==box.x0 || x_coordinate==box.x0+box.dx-1) && y_coordinate>=box.y0 && y_coordinate<box.y0+box.dy
      ||  (y_coordinate==box.y0 || y_coordinate==box.y0+box.dy-1) && x_coordinate>=box.x0 && x_coordinate<box.x0+box.dx );
}

/* 
 * check whether all the terminal pins are contained in some element in segment vector 
 * */
bool    CGR::isRouted ( CoarseNet &net ) {
  set <int> unvisited_terminal_pins = net.terminal_pins;

  for ( vector<Segment>::iterator itr_segment = net.sg.begin(); itr_segment != net.sg.end(); itr_segment ++ ) {
    for ( set<int>::iterator itr_pin = unvisited_terminal_pins.begin(); itr_pin!= unvisited_terminal_pins.end(); itr_pin ++ ) {
      if ( isInSegment ( *itr_pin, *itr_segment ) == true )
        unvisited_terminal_pins.erase ( itr_pin );
    }
  }
  return  unvisited_terminal_pins.empty();
}

/* 
 * compute the total overflow of a given routing
 */

bool  compare_pair_int_double ( const pair<int, double> &p1, const pair<int, double> &p2 ) {
  return  p1.second > p2.second;
}

bool  compare_pair_int_int ( const pair<int, int> &p1, const pair<int, int> &p2 ) {
  return  p1.second > p2.second;
}

bool  compare_pair_int_GridBox ( const pair<int, GridBox > &p1, const pair<int, GridBox> &p2 ) {
  return  p1.second.dx * p1.second.dy > p2.second.dx * p2.second.dy;
}

bool  compare_pair_string_double ( const pair<string, double> &p1, const pair<string, double> &p2 ) {
  return  p1.second < p2.second;
}

bool  CGR::compareDistBetweenTerminalPins ( const pair<int, int> &p1, const pair<int, int> &p2 ) {
  double  aW = fabs((double)(V[p1.first].x - V[p1.first].x) );
  double  aH = fabs((double)(V[p1.first].y - V[p1.first].y) );
  pair<double,double> costA(aW+aH,min(aW,aH)/max(aW,aH));
  double  bW = fabs((double)(V[p2.first].x - V[p2.first].x) );
  double  bH = fabs((double)(V[p2.first].y - V[p2.first].y) );
  pair<double,double> costB(bW+bH, min(bW,bH)/max(bW,bH));

  return  costA < costB;
}

int   CGR::selfIncrementalBoundingBox ( GridBox &box ) {

  int lowerleft_xcoordinate = box.x0;
  int lowerleft_ycoordinate = box.y0;
  int width = box.dx;
  int height = box.dy;
  int box_util = box.util;
  int box_cap = box.cap;

  vector< pair<string,double> > L_shape_segment_average_congestion;
  map < string, int > L_shape_segment_added_util;
  map < string, int > L_shape_segment_added_cap;

  //  
  if ( box.x0-1 >= 0 && box.y0-1 >= 0 ) {
    int total_util = 0;
    int total_cap = 0;
    //  lower segment
    for ( int i=box.x0; i<box.x0+box.dx; i++ ) {
      int node_id = xyzToGridNetTerminalId ( i,box.y0-1, 0 );
      total_util += E_2d[V[node_id].ne[1]].util;
      total_util += E_2d[V[node_id].ne[2]].util;
      total_cap += E_2d[V[node_id].ne[1]].cap;
      total_cap += E_2d[V[node_id].ne[2]].cap;
    }
    //  left segment
    for ( int j=box.y0; j<box.y0+box.dy; j++ ) {
      int node_id = xyzToGridNetTerminalId ( box.x0-1, j, 0 );
      total_util += E_2d[V[node_id].ne[0]].util;
      total_util += E_2d[V[node_id].ne[3]].util;
      total_cap += E_2d[V[node_id].ne[0]].cap;
      total_cap += E_2d[V[node_id].ne[3]].cap;
    }

    L_shape_segment_average_congestion.push_back ( make_pair ( "lower left", (double)(box_util+total_util)/(box_cap+total_cap)) );
    L_shape_segment_added_util.insert ( make_pair ( "lower left", total_util ) );
    L_shape_segment_added_cap.insert ( make_pair ( "lower left", total_cap ) );
  }
  //
  if ( box.x0-1 >= 0 && box.y0+box.dy < fullGridY ) {
    int total_util = 0;
    int total_cap = 0;
    // top segment 
    for ( int i=box.x0; i<box.x0+box.dx; i++ ) {
      int node_id = xyzToGridNetTerminalId ( i, box.y0+box.dy, 0 );
      total_util += E_2d[V[node_id].ne[1]].util;
      total_util += E_2d[V[node_id].ne[3]].util;
      total_cap += E_2d[V[node_id].ne[1]].cap;
      total_cap += E_2d[V[node_id].ne[3]].cap;
    }
    //  left segment
    for ( int j=box.y0; j<box.y0+box.dy; j++ ) {
      int node_id = xyzToGridNetTerminalId ( box.x0-1, j, 0 );
      total_util += E_2d[V[node_id].ne[0]].util;
      total_util += E_2d[V[node_id].ne[2]].util;
      total_cap += E_2d[V[node_id].ne[0]].cap;
      total_cap += E_2d[V[node_id].ne[2]].cap;
    }

    L_shape_segment_average_congestion.push_back ( make_pair ( "top left", (double)(box_util+total_util)/(box_cap+total_cap)) );
    L_shape_segment_added_util.insert ( make_pair ( "top left", total_util ) );
    L_shape_segment_added_cap.insert ( make_pair ( "top left", total_cap ) );
  }
  //
  if ( box.x0+box.dx < fullGridX && box.y0-1 >= 0 ) {
    int total_util = 0;
    int total_cap = 0;
    //  lower segment
    for ( int i=box.x0; i<box.x0+box.dx; i++ ) {
      int node_id = xyzToGridNetTerminalId ( i,box.y0-1, 0 );
      assert ( V[node_id].ne[0] != -1 );
      assert ( V[node_id].ne[2] != -1 );
      total_util += E_2d[V[node_id].ne[0]].util;
      total_util += E_2d[V[node_id].ne[2]].util;
      total_cap += E_2d[V[node_id].ne[0]].cap;
      total_cap += E_2d[V[node_id].ne[2]].cap;
    }
    //  right segment
    for ( int j=box.y0; j<box.y0+box.dy; j++ ) {
      int node_id = xyzToGridNetTerminalId ( box.x0+box.dx, j, 0 );
      assert ( V[node_id].ne[1] != -1 );
      assert ( V[node_id].ne[3] != -1 );
      total_util += E_2d[V[node_id].ne[1]].util;
      total_util += E_2d[V[node_id].ne[3]].util;
      total_cap += E_2d[V[node_id].ne[1]].cap;
      total_cap += E_2d[V[node_id].ne[3]].cap;
    }

    L_shape_segment_average_congestion.push_back ( make_pair ( "lower right", (double)(box_util+total_util)/(box_cap+total_cap)) );
    L_shape_segment_added_util.insert ( make_pair ( "lower right", total_util ) );
    L_shape_segment_added_cap.insert ( make_pair ( "lower right", total_cap ) );
  }
  //
  if ( box.x0+box.dx < fullGridX && box.y0+box.dy < fullGridY ) {
    int total_util = 0;
    int total_cap = 0;
    //  top segment
    for ( int i=box.x0; i<box.x0+box.dx; i++ ) {
      int node_id = xyzToGridNetTerminalId ( i, box.y0+box.dy, 0 );
      total_util += E_2d[V[node_id].ne[0]].util;
      total_util += E_2d[V[node_id].ne[3]].util;
      total_cap += E_2d[V[node_id].ne[0]].cap;
      total_cap += E_2d[V[node_id].ne[3]].cap;
    }
    //  right segment
    for ( int j=box.y0; j<box.y0+box.dy; j++ ) {
      int node_id = xyzToGridNetTerminalId ( box.x0+box.dx, j, 0 );
      total_util += E_2d[V[node_id].ne[1]].util;
      total_util += E_2d[V[node_id].ne[2]].util;
      total_cap += E_2d[V[node_id].ne[1]].cap;
      total_cap += E_2d[V[node_id].ne[2]].cap;
    }

    L_shape_segment_average_congestion.push_back ( make_pair ( "top right", (double)(box_util+total_util)/(box_cap+total_cap)) );
    L_shape_segment_added_util.insert ( make_pair ( "top right", total_util ) );
    L_shape_segment_added_cap.insert ( make_pair ( "top right", total_cap ) );
  }

  //  cout << "number of qualified candidate segments = " << L_shape_segment_average_congestion.size() << endl;
  //  for ( vector<pair<string,double> >::iterator it = L_shape_segment_average_congestion.begin(); it < L_shape_segment_average_congestion.end(); it++ )
  //    cout << (*it).first << "\t" << (*it).second << endl;
  sort ( L_shape_segment_average_congestion.begin(), L_shape_segment_average_congestion.end(), compare_pair_string_double );
  //  cout << "Adding segment : " << L_shape_segment_average_congestion[0].first << endl;
  if ( L_shape_segment_average_congestion[0].first == "lower left" ) {
    box.util += L_shape_segment_added_util["lower left"];
    box.cap += L_shape_segment_added_cap ["lower left"];
    box.x0 --; box.y0 --;
    box.dx ++; box.dy ++;
  }
  if ( L_shape_segment_average_congestion[0].first == "lower right" ) {
    box.util += L_shape_segment_added_util["lower right"];
    box.cap += L_shape_segment_added_cap ["lower right"];
    box.y0 --;
    box.dx ++; box.dy ++;
  }
  if ( L_shape_segment_average_congestion[0].first == "top left" ) {
    box.util += L_shape_segment_added_util["top left"];
    box.cap += L_shape_segment_added_cap ["top left"];
    box.x0 --; 
    box.dx ++; box.dy ++;
  }
  if ( L_shape_segment_average_congestion[0].first == "top right" ) {
    box.util += L_shape_segment_added_util["top right"];
    box.cap += L_shape_segment_added_cap ["top right"];
    box.dx ++; box.dy ++;
  }
  //  cout << "num of L-shape segments = " << L_shape_segment_average_congestion.size() << endl;
  //  for ( vector< pair<string, double> >::iterator it = L_shape_segment_average_congestion.begin(); it != L_shape_segment_average_congestion.end(); it ++ )
  //    cout << (*it).first << "\t" << (*it).second << endl;
  return  1;
}

GridBox CGR::buildBoudingBoxFromCongestedEdge ( int edge_id ) {
  int srcPoint = E_2d[edge_id].srcPoint;
  int snkPoint = E_2d[edge_id].snkPoint;
  GridBox   box;
  box.set_values ( V[srcPoint].x, V[srcPoint].y, V[snkPoint].x-V[srcPoint].x+1, V[snkPoint].y-V[srcPoint].y+1 );
  box.util = E_2d[edge_id].util;
  box.cap = E_2d[edge_id].cap;
  GridBox &ref_box = box;
  while ( (double)box.util/box.cap > TCR ) {
    int status = selfIncrementalBoundingBox ( ref_box );
    if ( status == 0 ) {
      cout << "ERROR : self increment bounding box" << endl;
      exit(0);
    }
  }
  return  box;
}

int     CGR::getCongestionMap ( void ) {

  E_2d.clear();
  V_2d.clear();

  vector< pair<int, double> > edge_congestion_map;

  /* 2-D projection */
  for ( int j=0; j< fullGridY; j++ )
    for ( int i=0; i< fullGridX-1; i++ )    {
      GridEdge    e;
      e.id = return_edge_id ( i,j,0,0 );
      e.srcPoint = xyzToGridNetTerminalId( i,j,0 ); 
      e.snkPoint = xyzToGridNetTerminalId( i+1,j,0 ); 
      e.type = "HORIZ";
      e.util = 0;
      e.cap = 0;
      for ( int k=0; k<numLayers; k++ ) {
        int edge_id = return_edge_id ( i,j,k,0 );
        e.util += E[edge_id].util;
        e.cap += E[edge_id].cap;
      }
      e.congestion_ratio = (double)e.util/e.cap;
      edge_congestion_map.push_back ( make_pair ( e.id, e.congestion_ratio ) );
      E_2d.push_back ( e );
    }
  for ( int i=0; i<fullGridX; i++ )   
    for ( int j=0; j< fullGridY-1; j++ )  {
      GridEdge    e;
      e.id = return_edge_id ( i,j,0,1 );
      e.srcPoint = xyzToGridNetTerminalId( i,j,0 ); 
      e.snkPoint = xyzToGridNetTerminalId( i,j+1,0 ); 
      e.type = "VERT";
      e.util = 0;
      e.cap = 0;
      for ( int k=0; k<numLayers; k++ ) {
        int edge_id = return_edge_id ( i,j,k,1 );
        e.util += E[edge_id].util;
        e.cap += E[edge_id].cap;
      }
      e.congestion_ratio = (double)e.util/e.cap;
      edge_congestion_map.push_back ( make_pair ( e.id, e.congestion_ratio ) );
      E_2d.push_back ( e );
    }
  /* sort congested edges in order of their congestion ratio */
  sort ( edge_congestion_map.begin(), edge_congestion_map.end(), compare_pair_int_double );

  cout << "2-D Projection Finished" << endl;

  /* the first elements of pair in bounding_box_per_edge are sorted according to congestion ratio */
  bounding_box_per_edge.clear();

  for ( vector< pair<int,double> >::iterator it = edge_congestion_map.begin(); it < edge_congestion_map.begin()+20; it ++ ) {
    int s = E_2d[(*it).first].srcPoint;
    int t = E_2d[(*it).first].snkPoint;

    GridBox box = buildBoudingBoxFromCongestedEdge ( (*it).first );
    box.printBox();
    bounding_box_per_edge.push_back ( make_pair((*it).first, box) );
  }

  return 1;
}

int   CGR::printCongestionMap ( void ) {

  ofstream congestion_map_file ( "congestion_map.txt" );
  for ( size_t i=0; i<E_2d.size(); i++ )
    if( E_2d[i].congestion_ratio > 1 )
      cout << i << "\t"<< V[E[i].srcPoint].z << "\t" << E_2d[i].congestion_ratio<< endl;
  return  1;
  cout.precision(3);
  for ( int j=0; j< fullGridY; congestion_map_file << endl,j++ )
    for ( int i=0; i< fullGridX-1; i++ )    
      congestion_map_file << fixed << E_2d[ return_edge_id(i,j,0,0) ].congestion_ratio<<" ";

  return 1;

  cout << endl << endl;
  for ( int j=0; j< fullGridY-1; j++ )
    for ( int i=0; i< fullGridX; i++ )    
      cout << fixed << E_2d[ return_edge_id(i,j,0,1) ].congestion_ratio<<" ";
}

vector<int> CGR::getEdgeVectorFromSegment ( Segment segment ) {
  vector<int> edge_vector;
  int src_point_id = segment.s;
  int snk_point_id = segment.t;
  if ( segment.type == "HORIZ" ) {
    for ( int i=V[src_point_id].x; i<V[snk_point_id].x; i++ )
      edge_vector.push_back ( return_edge_id(i, V[src_point_id].y, V[src_point_id].z, 0) );
    return  edge_vector;
  }
  if ( segment.type == "VERT" ) {
    for ( int j=V[src_point_id].y; j<V[snk_point_id].y; j++ )
      edge_vector.push_back ( return_edge_id(V[src_point_id].x, j, V[src_point_id].z, 1) );
    return  edge_vector;
  }
  if ( segment.type == "VIA" ) {
    for ( int k=V[src_point_id].z; k<V[snk_point_id].z; k++ )
      edge_vector.push_back ( return_edge_id(V[src_point_id].x, V[src_point_id].y, k, 2) );
    return  edge_vector;
  }
}

vector<int> CGR::getNodeVectorFromSegment ( Segment segment ) {
  vector<int> node_vector;
  int src_point_id = segment.s;
  int snk_point_id = segment.t;
  if ( segment.type == "HORIZ" ) {
    for ( int i=V[src_point_id].x; i<=V[snk_point_id].x; i++ )
      node_vector.push_back ( xyzToGridNetTerminalId ( i, V[src_point_id].y, V[src_point_id].z ) );
    return  node_vector;
  }
  if ( segment.type == "VERT" ) {
    for ( int j=V[src_point_id].y; j<=V[snk_point_id].y; j++ )
      node_vector.push_back ( xyzToGridNetTerminalId(V[src_point_id].x, j, V[src_point_id].z) );
    return  node_vector;
  }
  if ( segment.type == "VIA" ) {
    for ( int k=V[src_point_id].z; k<=V[snk_point_id].z; k++ )
      node_vector.push_back ( xyzToGridNetTerminalId(V[src_point_id].x, V[src_point_id].y, k) );
    return  node_vector;
  }
}

vector<int> CGR::getNodeVectorBetween ( int s, int t ) {
  vector<int> node_vector;
  int src_point_id = s;
  int snk_point_id = t;
  if ( V[s].x==V[t].x ) {
    for ( int i=V[src_point_id].x; i<=V[snk_point_id].x; i++ )
      node_vector.push_back ( xyzToGridNetTerminalId ( i, V[src_point_id].y, V[src_point_id].z ) );
    return  node_vector;
  }
  if ( V[s].y==V[t].y ) {
    for ( int j=V[src_point_id].y; j<=V[snk_point_id].y; j++ )
      node_vector.push_back ( xyzToGridNetTerminalId(V[src_point_id].x, j, V[src_point_id].z) );
    return  node_vector;
  }
  if ( V[s].z==V[t].z ) {
    for ( int k=V[src_point_id].z; k<=V[snk_point_id].z; k++ )
      node_vector.push_back ( xyzToGridNetTerminalId(V[src_point_id].x, V[src_point_id].y, k) );
    return  node_vector;
  }
}

bool    CGR::isInNet ( int edge_id_number, CoarseNet &net ) {
  for ( int i=0; i<net.sg.size(); i++ )
    if ( isInNetSegment ( edge_id_number, net.sg[i] ) )
      return  true;
  return  false;
}

bool    CGR::isInNetSegment ( int edge_id_number, Segment segment_in_net ) {
  int src_id_in_edge = E[edge_id_number].srcPoint;
  int snk_id_in_edge = E[edge_id_number].snkPoint;
  int src_id_in_segment = segment_in_net.s;
  int snk_id_in_segment = segment_in_net.t;
  if ( segment_in_net.type == "HORIZ" ) 
    return  ( V[src_id_in_edge].y==V[src_id_in_segment].y && V[src_id_in_edge].z==V[src_id_in_segment].z
        && V[src_id_in_edge].x>=V[src_id_in_segment].x && V[src_id_in_edge].x<=V[src_id_in_segment].x );
  if ( segment_in_net.type == "VERT" ) 
    return  ( V[src_id_in_edge].x==V[src_id_in_segment].x && V[src_id_in_edge].z==V[src_id_in_segment].z
        && V[src_id_in_edge].y>=V[src_id_in_segment].y && V[src_id_in_edge].y<=V[src_id_in_segment].y );
  if ( segment_in_net.type == "VIA" ) 
    return  ( V[src_id_in_edge].x==V[src_id_in_segment].x && V[src_id_in_edge].y==V[src_id_in_segment].y
        && V[src_id_in_edge].z>=V[src_id_in_segment].z && V[src_id_in_edge].z<=V[src_id_in_segment].z );
}

bool    CGR::isOverlappingBoxes ( GridBox box1, GridBox box2 ) {
  return ( box1.x0 < box2.x0+box2.dx && box2.x0 < box1.x0+box1.dx && box1.y0 < box2.y0+box2.dy && box2.y0 < box1.y0+box1.dy );
}

/* check if a net is connected 
 *  reading its edge set */
bool  CGR::isConnected ( CoarseNet &net ) {
  /* build a graph */
  bool  debug_mode = true ;
  map<int,set<int> >  tree_in_adjacent_form;
  for ( set<int>::iterator itr_edge = net.edges.begin(); itr_edge != net.edges.end(); itr_edge++ ) {
    int s = E[(*itr_edge)].srcPoint;
    int t = E[(*itr_edge)].snkPoint;
    if ( tree_in_adjacent_form.count ( s ) != 0 )
      tree_in_adjacent_form[s].insert ( t );
    else {
      set<int>  myset;
      myset.insert ( t );
      tree_in_adjacent_form.insert ( make_pair(s, myset) );
    }
    if ( tree_in_adjacent_form.count ( t ) != 0 )
      tree_in_adjacent_form[t].insert ( s );
    else {
      set<int>  myset;
      myset.insert ( s );
      tree_in_adjacent_form.insert ( make_pair(t, myset) );
    }
  }
  /* implement a BFS and check if the number of visited nodes equals to node number of graph */
  queue<int>  Q;
  set<int>    V;
  int v = (*(tree_in_adjacent_form.begin())).first;  // this can be any node in graph
  Q.push ( v );
  V.insert ( v );
  while ( Q.empty()==false ) {
    int t = Q.front();
    Q.pop();
    for ( set<int>::iterator it = tree_in_adjacent_form[t].begin(); it!= tree_in_adjacent_form[t].end(); it++ ) {
      if ( V.find(*it)==V.end() ) {
        V.insert ( *it );
        Q.push ( *it );
      }
    }
  }
  return  V.size()==tree_in_adjacent_form.size();
}

/* if exists boundary pins
 *  then divide them into several disjoint sets */
  void  CGR::splitBoundaryTerminalPins ( CoarseNet &net ) {
    if ( net.boundary_terminal_pins.size() == 0 )
      return;
    /* use segment vector to determine whether they are connected or not */
    /* build a graph */
    map<int,set<int> >  tree_in_adjacent_form;
    for ( size_t i=0; i< net.sg.size(); i++ ) {
      vector<int> edge_vector = getEdgeVectorFromSegment ( net.sg[i] );
      for ( vector<int>::iterator it = edge_vector.begin(); it!= edge_vector.end(); it++ ) {
        int s = E[(*it)].srcPoint;
        int t = E[(*it)].snkPoint;
        if ( tree_in_adjacent_form.count ( s ) != 0 )
          tree_in_adjacent_form[s].insert ( t );
        else {
          set<int>  myset;
          myset.insert ( t );
          tree_in_adjacent_form.insert ( make_pair(s, myset) );
        }
        if ( tree_in_adjacent_form.count ( t ) != 0 )
          tree_in_adjacent_form[t].insert ( s );
        else {
          set<int>  myset;
          myset.insert ( s );
          tree_in_adjacent_form.insert ( make_pair(t, myset) );
        }
      }
    }
    set<int>    U;  //  unvisited boundary pins
    U.insert ( net.boundary_terminal_pins.begin(), net.boundary_terminal_pins.end() );
    while ( U.empty()==false ) {
      set<int>  connected_boundary_pins;
      int v = *(U.begin());
      set<int>    V;
      queue<int>  Q;
      Q.push ( v );
      V.insert ( v );
      while ( Q.empty()==false ) {
        int t = Q.front();
        Q.pop();
        for ( set<int>::iterator it = tree_in_adjacent_form[t].begin(); it!= tree_in_adjacent_form[t].end(); it++ ) {
          if ( V.find(*it)==V.end() ) {
            V.insert ( *it );
            Q.push ( *it );
          }
        }
      }
      for ( set<int>::iterator it = U.begin(); it != U.end(); ) {
        if ( V.find(*it) != V.end() ) {
          U.erase ( it++ );
          connected_boundary_pins.insert ( *it );
        }
        else
          ++it;
      }
      net.disjoint_boundary_terminal_pins.push_back ( connected_boundary_pins );
    }
  }

int     CGR::pt_dist ( int  v1, int v2 ) {
  NetTerminal t1 = V[v1];
  NetTerminal t2 = V[v2];
  return  fabs(t1.x-t2.x) + fabs(t1.y-t2.y);
}

bool    CGR::isAllIndependentSegments ( CoarseNet &net ) {
  set<int>  edge_set;
  for ( size_t i=0; i<net.sg.size(); i++ ) {
    vector<int> segment_edge_vector = getEdgeVectorFromSegment ( net.sg[i] );
    for ( size_t j=0; j< segment_edge_vector.size(); j++ ) {
      if ( edge_set.find ( segment_edge_vector[j] ) != edge_set.end() )
        return  false;
      edge_set.insert ( segment_edge_vector[j] );
    }
  }
  return  true;
}

bool    CGR::isLegalRoute ( CoarseNet &net ) {
  if ( isRouted ( net ) == false ) {
    /* all the terminal pins are visited */
    cout<<"ERROR : isRouted false "<<endl;
  }
  if ( isConnected( net ) == false ) {
    /* all the edges are connected */
    cout<<"ERROR : isConnected false "<<endl;
  }
  return  isRouted(net) && isConnected(net);
}

set<int>    CGR::getFlatSegment ( int s, int t ) {
  if ( s>t ) {
    int tmp = s;  s = t; t = tmp;
  }
  set<int>  edge_set;
  assert (  V[s].x==V[t].x && V[s].y==V[t].y || V[s].y==V[t].y && V[s].z==V[t].z ||  V[s].x==V[t].x && V[s].z==V[t].z ); 
  /* return integer set containing all the edges connecting two given nodes in form of flat segment */
  if ( V[s].x!=V[t].x ) {
    for ( int i = V[s].x; i < V[t].x; i++ ) 
      edge_set.insert ( return_edge_id ( i, V[s].y, V[s].z, 0 ) );
  }
  if ( V[s].y!=V[t].y ) {
    for ( int i = V[s].y; i < V[t].y; i++ ) 
      edge_set.insert ( return_edge_id ( V[s].x, i, V[s].z, 1 ) );
  }
  if ( V[s].z!=V[t].z ) {
    for ( int i = V[s].z; i < V[t].z; i++ ) 
      edge_set.insert ( return_edge_id ( V[s].x, V[s].y, i, 2 ) );
  }
  return  edge_set;
}

void  CGR::printSegmentEdges ( Segment segment ) {
  cout << "\t(" << V[segment.s].x << "," << V[segment.s].y << "," << V[segment.s].z << ") - (";
  cout << V[segment.t].x << "," << V[segment.t].y << "," << V[segment.t].z << ")" << endl;
}

void  CGR::printEdgeSet ( set<int> edges ) {
  for ( set<int>::iterator it = edges.begin(); it != edges.end(); it++ ) {
    int s = E[*it].srcPoint;
    int t = E[*it].snkPoint;
    printEdge ( *it );
  }
  cout << endl;
}

void  CGR::printSegmentVector ( vector<Segment> sg ) {
  for ( size_t  i=0;  i<sg.size();  i++ )
    printSegmentEdges ( sg[i] );
}

void  CGR::printCrossingPointsOnSegments ( CoarseNet &net ) {
  for ( vector<set<int> >::iterator it = net.crossing_points_on_segments.begin(); it != net.crossing_points_on_segments.end(); it++ ) {
    cout << "---" << endl;
    printSegmentEdges ( net.sg[it-net.crossing_points_on_segments.begin()] );
    for ( set<int>::iterator it2 = (*it).begin(); it2 != (*it).end(); it2++ ) {
      cout << "\t(" << V[*it2].x << "," << V[*it2].y << "," << V[*it2].z << ")" << endl;
    }
  }
}

void  CGR::printVertices ( vector<int>  vxs ) {
  for ( size_t i=0; i< vxs.size(); i++ )
    cout << "\t(" << V[vxs[i]].x << "," << V[vxs[i]].y << "," << V[vxs[i]].z << ")" << endl;
}

void  CGR::printEdge ( int edge_id ) {
  int s = E[edge_id].srcPoint;
  int t = E[edge_id].snkPoint;
  cout << "edge id : " << edge_id << "\t(" << V[s].x <<","<<V[s].y<<","<<V[s].z<<")-(";
  if ( E[edge_id].cap != 0 )
    cout << V[t].x <<","<<V[t].y<<","<<V[t].z<<") : " << E[edge_id].type << " " << E[edge_id].cap <<" " << E[edge_id].util << " " << E[edge_id].weight 
                                                         << "\t" << (double)E[edge_id].util/E[edge_id].cap << endl;
  else
    cout << V[t].x <<","<<V[t].y<<","<<V[t].z<<") : " << E[edge_id].type << " " << E[edge_id].cap <<" " << E[edge_id].util << " " << E[edge_id].weight << "\t" << endl;
}

void  CGR::printEdge_2d ( int edge_id ) {
  int s = E_2d[edge_id].srcPoint;
  int t = E_2d[edge_id].snkPoint;
  cout << "(" << V[s].x <<","<<V[s].y<<","<<V[s].z<<")-(";
  cout << V[t].x <<","<<V[t].y<<","<<V[t].z<<")\tcap=" << E_2d[edge_id].cap <<" util=" << E_2d[edge_id].util << "\t" << E_2d[edge_id].congestion_ratio << endl;
}

void  CGR::printNode ( int node_id ) {
  cout << "node : (" << V[node_id].x<<","<< V[node_id].y<<"," << V[node_id].z << ")" << endl;
}

void  CGR::printNode_2d ( int node_id ) {
  cout << "node : (" << V[node_id].x<<","<< V[node_id].y<< ")\t" << V_2d[node_id].util << " " << V_2d[node_id].cap << " " << V_2d[node_id].congestion_ratio << endl;
  //  for ( size_t j=0; j<4; j++ )
  //    if ( V[node_id].ne[j] != -1 )
  //      printEdge_2d ( V_2d[node_id].ne[j] );
}

void  CGR::printEdgeWeightInSegment ( Segment segment ) {
  vector<int> edge_vector = getEdgeVectorFromSegment ( segment );
  for ( size_t i=0; i< edge_vector.size(); i++ ) {
    int s = E[edge_vector[i]].srcPoint;
    int t = E[edge_vector[i]].snkPoint;
    cout << "(" << V[s].x <<","<<V[s].y<<","<<V[s].z<<")-(";
    cout << V[t].x <<","<<V[t].y<<","<<V[t].z<<")\t" 
      << E[edge_vector[i]].cap  << " " 
      << E[edge_vector[i]].util << " " 
      << E[edge_vector[i]].weight << endl;
  }
}

void  CGR::printIntVector ( vector<int> int_vector ) {
  for ( size_t i=0; i<int_vector.size(); i++ )
    cout << int_vector[i] << " ";
  cout << endl;
}

void  CGR::printNet ( CoarseNet &net ) {
  cout << "net id " << net.old_index << endl;
  cout << "\tterminal pins : " << endl;
  vector<int>   terminal_pins ( net.terminal_pins.begin(), net.terminal_pins.end() );
  printVertices ( terminal_pins );
  cout << "\tsegments : " << endl;
  printSegmentVector ( net.sg );
}

void  CGR::printSubNet ( TwoTerCoarseNet &snet ) {
  cout << "FROM : " ; printNode ( snet.s );
  cout << "TO : " ; printNode ( snet.t );
  printEdgeSet ( snet.edges );
}

vector<int>   CGR::getAdjacentNodes ( vector<int> nodes, set<int> edges, int u ) {
  vector<int> neighbor_nodes;
  for ( int i=0; i< 6; i++ ) {
    if ( V[u].ne[i]!=-1 && edges.find(V[u].ne[i])!=edges.end() ) {
      assert ( V[u].nv[i] != -1 );
      neighbor_nodes.push_back ( V[u].nv[i] );
    }
  }
  return  neighbor_nodes;
}

int   CGR::getEdgeIdWithTwoEndingPoints ( int u, int v ) {
  if ( V[u].x != V[v].x ) {
    assert ( V[u].y==V[v].y && V[u].z==V[v].z );
    assert ( abs(V[u].x - V[v].x)==1 );
    return  return_edge_id ( min(V[u].x, V[v].x), V[u].y, V[u].z, 0 );
  }
  if ( V[u].y != V[v].y ) {
    assert ( V[u].x==V[v].x && V[u].z==V[v].z );
    assert ( abs(V[u].y - V[v].y)==1 );
    return  return_edge_id ( V[u].x, min(V[u].y, V[v].y), V[u].z, 1 );
  }
  if ( V[u].z != V[v].z ) {
    assert ( V[u].y==V[v].y && V[u].x==V[v].x );
    assert ( abs(V[u].z - V[v].z)==1 );
    return  return_edge_id ( V[u].x, V[u].y, min(V[u].z, V[v].z), 2 );
  }
}

int   CGR::getNearestUnvisitedTerminalPin ( vector<int> nodes, map<int, set<int> > tree_in_adjacent_form, int starting_terminal_pin, set<int> visited_nodes, set<int> &path ) {
  //  Assigned variables :
  //    set<int> &path
  //    of course a node id as a return !
  queue<int>  q;
  set<int>    alreadly_visited;
  map<int,int>  previous_node;

  q.push ( starting_terminal_pin );
  alreadly_visited.insert ( starting_terminal_pin );
  while ( q.size() != 0 ) {
    int t = q.front();
    q.pop();
    vector<int> adjacent_nodes ( tree_in_adjacent_form[t].begin(), tree_in_adjacent_form[t].end() );
    for ( vector<int>::iterator it = adjacent_nodes.begin(); it != adjacent_nodes.end(); it ++ ) {
      if ( alreadly_visited.find(*it)==alreadly_visited.end() ) {
        q.push ( *it );
        alreadly_visited.insert ( *it );
        previous_node.insert ( make_pair (*it,t) );
        //  check if the newly visited node is target
        int current_node = *it;
        if ( find(nodes.begin(), nodes.end(), current_node)!=nodes.end()     //  is terminal pin
            &&  visited_nodes.find(current_node)==visited_nodes.end()  ) {   //  not visited yet 
          //  back-trace
          while ( current_node != starting_terminal_pin ) {
            path.insert ( getEdgeIdWithTwoEndingPoints ( current_node, previous_node[current_node] ) );
            current_node = previous_node[current_node];
          }
          return  *it;
        }
      }
    }
  }
  return  -1;
}

void    CGR::findNonOverlappingBoxes (int number_of_boxes ) {
  vector<pair<int,GridBox> >::iterator it = cgr.bounding_box_per_edge.begin();
  while ( bounding_boxes_to_solve.size() < number_of_boxes ) {
    if ( it == cgr.bounding_box_per_edge.end() )
      break;
    bool  valid = true;
    for ( size_t i=0; i < bounding_boxes_to_solve.size(); i++ ) {
      if ( cgr.isOverlappingBoxes ( bounding_boxes_to_solve[i], (*it).second ) ) {
        valid = false;
        it++;
        break;
      }
    }
    if ( valid==false )
      continue;
    bounding_boxes_to_solve.push_back ( (*it).second );
    (*it).second.printBox();
  }
  cout << "Select " << bounding_boxes_to_solve.size() << " bounding boxes" << endl;
}

#endif
